Class sjl.Algo
All Packages Class Hierarchy This Package Previous Next Index
Class sjl.Algo
java.lang.Object
|
+----sjl.Algo
- public class Algo
- extends Object
The Algo class contains static methods that implements the generic
algorithms.
Certain shorthand notaions are throughout the documentation of the
algorithm functions.
N
is the number of elements in the range
[first, last)
.
N1
is the number of elements in the range
[first1, last1)
.
N2
is the number of elements in the range
[first2, last2)
.
func(...)
means the function object func
is performed.
pred(...)
means the predicate object pred
is tested.
...
in a range means that the end of the range
depends on some other parameters,
typically N
.
Copyright © 1996 Finn Bock
-
sortChunkSize
- Used in merge sort.
-
sortThreshold
- Used in quick sort.
-
tmp_buffer_size
- The maximum size of temporary buffers.
-
accumulate(InputIterator, InputIterator, Object, Function2)
- Accumulate over the range.
-
adjacent_difference(InputIterator, InputIterator, OutputIterator, Function2)
- Computes the adjancent difference of the elements in the range.
-
adjacent_find(ForwardIterator, ForwardIterator)
- Find the first instance of two equal adjacent elements.
-
adjacent_find(ForwardIterator, ForwardIterator, Predicate2)
- Find the first instance of two adjacent elements
satisfying a predicate.
-
advance(BidirectionalIterator, int)
- Advance the iterator a number of times.
-
advance(InputIterator, int)
- Advance the iterator a number of times.
-
advance(RandomIterator, int)
- Advance the iterator a number of times.
-
binary_search(ForwardIterator, ForwardIterator, Object, Predicate2)
- Returns true is the value is in the range.
-
copy(InputIterator, InputIterator, OutputIterator)
- Copy elements from one range to another.
-
copy_backward(BidirectionalIterator, BidirectionalIterator, BidirectionalIterator)
- Copy elements from one range to another, backwards.
-
count(InputIterator, InputIterator, Object)
- Return the number of elements in the range equal to a value.
-
count(InputIterator, InputIterator, Predicate1)
- Return the number of element satisfying a predicate.
-
equal(InputIterator, InputIterator, InputIterator)
-
Compares to ranges.
-
equal(InputIterator, InputIterator, InputIterator, Predicate2)
- Compares to ranges using a predicate.
-
equal_range(ForwardIterator, ForwardIterator, Object, Predicate2)
- Find the largest subrange into which a value can be inserted
without violation the ordering.
-
fill(ForwardIterator, ForwardIterator, Object)
- Assign a value to all elements in the range.
-
fill(OutputIterator, int, Object)
- Assign a value to all elements in the range.
-
find(InputIterator, InputIterator, Object)
- Find the first elements matching a specified value.
-
find(InputIterator, InputIterator, Predicate1)
- Find the first element satisfying a predicate.
-
for_each(InputIterator, InputIterator, Function1)
- Apply a function object to each element in the range.
-
generate(ForwardIterator, ForwardIterator, Function0)
- Assign the result of a function object to all elements in the range.
-
generate(OutputIterator, int, Function0)
- Assign the result of a function object to all elements in the range.
-
includes(InputIterator, InputIterator, InputIterator, InputIterator, Predicate2)
- Return
true
if all the elements in range2 also is in range2.
-
inner_product(InputIterator, InputIterator, InputIterator, Object, Function2, Function2)
- Compute the inner product of two ranges.
-
inplace_merge(BidirectionalIterator, BidirectionalIterator, BidirectionalIterator, Predicate2)
- Merge the two sorted ranges and place the result into the result range.
-
iota(ForwardIterator, ForwardIterator, Object, Function2, Object)
- XXX.
-
iter_swap(ForwardIterator, ForwardIterator)
- Swap the elements that the iterators points to.
-
lexicographical_compare(InputIterator, InputIterator, InputIterator, InputIterator, Predicate2)
- Compares two sequences lexicographically and return true if
range1 is less than range2.
-
lower_bound(ForwardIterator, ForwardIterator, Object, Predicate2)
- Find the first position into which a value can be inserted
without violation the ordering.
-
make_heap(RandomIterator, RandomIterator, Predicate2)
- Create a heap out of a sequence.
-
max(char, char)
- Returns the larger of the two characters.
-
max(int, int)
- Returns the larger of the two integers.
-
max(Object, Object, Predicate2)
- Returns the larger of two objects.
-
max_element(ForwardIterator, ForwardIterator, Predicate2)
- Returns the first iterator pointing to the maximal element in the range.
-
merge(InputIterator, InputIterator, InputIterator, InputIterator, OutputIterator, Predicate2)
- Merge the two sorted ranges and place the result into the result range.
-
min(char, char)
- Returns the smaller of the two characters.
-
min(int, int)
- Returns the smaller of the two integers.
-
min(Object, Object, Predicate2)
- Returns the smaller of two objects.
-
min_element(ForwardIterator, ForwardIterator, Predicate2)
- Returns the first iterator pointing to the minimal element in the range.
-
mismatch(InputIterator, InputIterator, InputIterator)
- Find the first instance of mismatch between two ranges.
-
mismatch(InputIterator, InputIterator, InputIterator, Predicate2)
- Find the first instance of mismatch between two ranges when
comparing with a predicate.
-
next_permutation(BidirectionalIterator, BidirectionalIterator, Predicate2)
- Permutates the sequence into its successor.
-
nth_element(RandomIterator, RandomIterator, RandomIterator, Predicate2)
- Place an element of a sequence in the location where it
would be if the sequence was sorted.
-
partial_sum(InputIterator, InputIterator, OutputIterator, Function2)
- Computes the partial sum of the elements in the range.
-
partion(BidirectionalIterator, BidirectionalIterator, Predicate1)
- Place all elements satisfying a predicate before those
element than to not satisfy the predicate.
-
pop_heap(RandomIterator, RandomIterator, Predicate2)
- Remove the largest value from the heap.
-
prev_permutation(BidirectionalIterator, BidirectionalIterator, Predicate2)
- Permutates the sequence into its predecessor.
-
push_heap(RandomIterator, RandomIterator, Predicate2)
- Place a new value into the heap.
-
random_shuffle(RandomIterator, RandomIterator)
- Randomly reorders the elements in the range.
-
random_shuffle(RandomIterator, RandomIterator, RandomGenerator)
- Randomly reorders the elements in the range using
a random generator.
-
remove(ForwardIterator, ForwardIterator, Object)
- Remove all elements in the range which match a value.
-
remove(ForwardIterator, ForwardIterator, Predicate1)
- Remove all elements in the range which satisfy a predicate.
-
remove_copy(InputIterator, InputIterator, OutputIterator, Object)
- Copy all elements in the range except those matching a value.
-
remove_copy(InputIterator, InputIterator, OutputIterator, Predicate1)
- Copy all elements in the range except those which satidfy a predicate.
-
replace(ForwardIterator, ForwardIterator, Object, Object)
- Replace all elements in the range which match a value,
with another value.
-
replace(ForwardIterator, ForwardIterator, Predicate1, Object)
- Replace all element in the range which satisfy a predicate with
another value.
-
reverse(BidirectionalIterator, BidirectionalIterator)
- Reverse the elements in the range.
-
reverse(RandomIterator, RandomIterator)
- Reverse the elements in the range.
-
rotate(BidirectionalIterator, BidirectionalIterator, BidirectionalIterator)
- Shift elements in the range leftwards.
-
rotate(ForwardIterator, ForwardIterator, ForwardIterator)
- Shift elements in the range leftwards.
-
rotate(RandomIterator, RandomIterator, RandomIterator)
- Shift elements in the range leftwards.
-
rotate_copy(ForwardIterator, ForwardIterator, ForwardIterator, OutputIterator)
- Shift elements in the range leftwards, placing the result
into another range.
-
search(ForwardIterator, ForwardIterator, ForwardIterator, ForwardIterator)
- Find the first instance in a range where of a subsequence occur.
-
search(ForwardIterator, ForwardIterator, ForwardIterator, ForwardIterator, Predicate2)
- Find the first instance in a range where of a subsequence occur
when comparing using a predicate.
-
set_difference(InputIterator, InputIterator, InputIterator, InputIterator, OutputIterator, Predicate2)
- Create the difference of the two ranges.
-
set_intersection(InputIterator, InputIterator, InputIterator, InputIterator, OutputIterator, Predicate2)
- Create the intersection of the two ranges.
-
set_symmetric_difference(InputIterator, InputIterator, InputIterator, InputIterator, OutputIterator, Predicate2)
- Create the symmetric difference of the two ranges.
-
set_union(InputIterator, InputIterator, InputIterator, InputIterator, OutputIterator, Predicate2)
- Create the union of the two ranges.
-
sort(RandomIterator, RandomIterator, Predicate2)
- Sort the elements in the range according to the
comparison predicate pred.
-
sort_heap(RandomIterator, RandomIterator, Predicate2)
- Turns the heap into a sorted sequence.
-
stable_partion(BidirectionalIterator, BidirectionalIterator, Predicate1)
- Place all elements satisfying a predicate before those
element than to not satisfy the predicate while maintaing
the relative order of elements.
-
stable_sort(RandomIterator, RandomIterator, Predicate2)
- Sort the elements in the range according to the
comparison predicate pred.
-
swap_ranges(ForwardIterator, ForwardIterator, ForwardIterator)
- Swap the elements of two ranges.
-
transform(InputIterator, InputIterator, InputIterator, OutputIterator, Function2)
- Execute a function object on every two elements in two ranges, storing
the result into a third (or the same) range.
-
transform(InputIterator, InputIterator, OutputIterator, Function1)
- Execute a function object on every element in a range, storing
the result into another (or the same) range.
-
unique(ForwardIterator, ForwardIterator)
- Remove all but the first element from every consecutive
group of equal elements.
-
unique(ForwardIterator, ForwardIterator, Predicate2)
- Remove all but the first element from every consecutive
group of equal elements when comparing with a predicate.
-
unique_copy(InputIterator, InputIterator, OutputIterator)
- Copy only the first element from every consecutive
group of equal elements.
-
unique_copy(InputIterator, InputIterator, OutputIterator, Predicate2)
- Copy only the first element from every consecutive
group of equal elements when comparing with a predicate.
-
upper_bound(ForwardIterator, ForwardIterator, Object, Predicate2)
- Find the furthermost position into which a value can be inserted
without violation the ordering.
tmp_buffer_size
public static int tmp_buffer_size
- The maximum size of temporary buffers. Temporary buffer are used
while sorting.
sortThreshold
public static int sortThreshold
- Used in quick sort.
sortChunkSize
public static int sortChunkSize
- Used in merge sort.
advance
public static void advance(InputIterator i,
int distance)
- Advance the iterator a number of times.
The iterator
i
is advanced distance
times by calling next()
.
- Parameters:
- i - The iterator to be moved forward.
- distance - The number of times the iterator must be moved.
advance
public static void advance(BidirectionalIterator i,
int distance)
- Advance the iterator a number of times.
The iterator
i
is advanced distance
times by calling next()
.
distance
can be negative, is this case the iterator
is moved backwards by calling prev()
.
- Parameters:
- i - The iterator to be moved forward or backward.
- distance - The number of times the iterator must be moved.
advance
public static void advance(RandomIterator i,
int distance)
- Advance the iterator a number of times.
The iterator
i
is advanced distance
position by calling next(distance)
.
- Parameters:
- i - The iterator to be moved forward or backward.
- distance - The number of position the iterator must be moved.
for_each
public static Function1 for_each(InputIterator first,
InputIterator last,
Function1 func)
- Apply a function object to each element in the range.
for_each
applies func
to each element
in the range [first, last)
.
func
is assumed not to change the elements.
func
is applied exactly N
times.
If func
returns a result, the result is ignored.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- func - the function object that is perform.
- Returns:
- func
find
public static InputIterator find(InputIterator first,
InputIterator last,
Object value)
- Find the first elements matching a specified value.
Find returns the first iterator
i
in the range
[first,last)
for which the following condition
holds: i.get().equals(value)
.
If the no such iterator is found, last
is returned.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- value - that must match.
- Returns:
- the iterator pointing to the found element.
find
public static InputIterator find(InputIterator first,
InputIterator last,
Predicate1 pred)
- Find the first element satisfying a predicate.
Find returns the first iterator
i
in the range
[first, last)
for which the following condition
holds: pred(i.get(), value)
.
If the no such iterator is found, last
is returned.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - the predicate that must be true,
- Returns:
- the iterator pointing to the found element.
adjacent_find
public static ForwardIterator adjacent_find(ForwardIterator first,
ForwardIterator last)
- Find the first instance of two equal adjacent elements.
adjacent_find
returns the first iterator i
in the range [first,last)
where
i.get().equal(i.next().get()) == true
If no such iterator is found, last
is returned.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- Returns:
- the iterator pointing to the found element.
adjacent_find
public static ForwardIterator adjacent_find(ForwardIterator first,
ForwardIterator last,
Predicate2 pred)
- Find the first instance of two adjacent elements
satisfying a predicate.
adjacent_find
returns the first iterator in the range
[first,last)
where
pred(i.get(), i.next().get()) == true
.
If no such iterator is found, last
is returned.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - the predicate that must be true.
- Returns:
- the iterator pointing to the found element.
count
public static int count(InputIterator first,
InputIterator last,
Object value)
- Return the number of elements in the range equal to a value.
count
returns the number of iterator i
in the range [first,last)
where
i.get().equals(value) == true
.
Note that this differs from STL.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- value - the object which is tested against.
- Returns:
- the number of elements matching value.
count
public static int count(InputIterator first,
InputIterator last,
Predicate1 pred)
- Return the number of element satisfying a predicate.
count
returns the number of iterators i
in the range [first,last) where
pred(i.get()) == true.
Note that this differs from STL.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - the predicate that must be true.
- Returns:
- the number of elements for which pred returned true.
mismatch
public static Pair mismatch(InputIterator first1,
InputIterator last1,
InputIterator first2)
- Find the first instance of mismatch between two ranges.
mismatch
returns the pair of iterators
i
and j
such that j
and
i
is the first iterators in the range
[first1, last1)
for which
i.get().equals(j.get()) == false
.
If such iterators is not found, last1
and the corresponding
iterator from first2
is returned.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- Returns:
- a pair of iterators pointing to first elements not matching.
mismatch
public static Pair mismatch(InputIterator first1,
InputIterator last1,
InputIterator first2,
Predicate2 pred)
- Find the first instance of mismatch between two ranges when
comparing with a predicate.
mismatch
returns the pair of iterators i
and j
such that j
and i
is
the first iterators in the range [first1,last1)
for which pred(i.get(), j.get()) == false
.
If such iterators is not found, last1
and the corresponding
iterator from first2
is returned.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- pred - The predicate used when comparing.
- Returns:
- a pair of iterators pointing to first elements not matching.
equal
public static boolean equal(InputIterator first1,
InputIterator last1,
InputIterator first2)
- Compares to ranges.
equal
returns true
if every element in the
range [first1,last1)
is equal
to the corresponding element in the second range.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- Returns:
- A boolean indication whether the ranges are equal.
equal
public static boolean equal(InputIterator first1,
InputIterator last1,
InputIterator first2,
Predicate2 pred)
- Compares to ranges using a predicate.
equal
returns true
if every element in the
range [first1,last1)
is equal
to the corresponding element in the other range.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- pred - The predicate used when comparing.
- Returns:
- A boolean indication whether the ranges are equal.
search
public static ForwardIterator search(ForwardIterator first1,
ForwardIterator last1,
ForwardIterator first2,
ForwardIterator last2)
- Find the first instance in a range where of a subsequence occur.
search
Finds a subsequence of equal values in a sequence.
Returns the first iterator i
in the range
[first1,last1)
where the subsequence
[first2,last2)
is found.
If no such subsequence is found, last1
is returned.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- last2 - The end of the second range
- Returns:
- A iterator pointer to the start of subsequence found.
search
public static ForwardIterator search(ForwardIterator first1,
ForwardIterator last1,
ForwardIterator first2,
ForwardIterator last2,
Predicate2 pred)
- Find the first instance in a range where of a subsequence occur
when comparing using a predicate.
search
finds a subsequence of equal values in a sequence.
Returns the first iterator i
in the range
[first1,last1)
where the subsequence
[first2,last2)
is found.
If no such subsequence is found, last1
is returned.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- last2 - The end of the second range
- pred - The predicate used for comparing elements in the ranges.
- Returns:
- A iterator pointer to the start of subsequence found.
copy
public static OutputIterator copy(InputIterator first,
InputIterator last,
OutputIterator result)
- Copy elements from one range to another.
copy
the elements from the range [first, last)
to result.
The result of copy is undefined if result is in the range
[first,last)
.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- result - The destination where the element are copied to.
- Returns:
- A iterator pointer to past-the-end of the result sequence.
copy_backward
public static BidirectionalIterator copy_backward(BidirectionalIterator first,
BidirectionalIterator last,
BidirectionalIterator result)
- Copy elements from one range to another, backwards.
copy_backward
copies the elements from the range
[first, last)
to result starting from
last.prev()
and proceeding to first
.
It should be used instead of copy()
when last
is in the range [result-N,result), result)
.
The result of copy_backward
is undefined if result is
in the range [first, last)
.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- result - The end of the result range.
- Returns:
- A iterator pointer to beginning of the result sequence.
iter_swap
public static void iter_swap(ForwardIterator a,
ForwardIterator b)
- Swap the elements that the iterators points to.
swap_ranges
public static ForwardIterator swap_ranges(ForwardIterator first1,
ForwardIterator last1,
ForwardIterator first2)
- Swap the elements of two ranges.
swap_ranges
swaps each element in the ranges
[first1,last1) and [first2,...)
.
The result of swap_ranges
is undefined if the two
ranges overlap.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- Returns:
- A iterator pointing past-the-end of the second range.
transform
public static OutputIterator transform(InputIterator first,
InputIterator last,
OutputIterator result,
Function1 func)
- Execute a function object on every element in a range, storing
the result into another (or the same) range.
transform
assigns through every iterator in the
range [result,...)
a new corresponding value equal to func(i.get())
for
each i
in the range [first,last)
.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- result - The beginning of the result range
- Returns:
- An iterator pointing past-the-end of the result range.
transform
public static OutputIterator transform(InputIterator first1,
InputIterator last1,
InputIterator first2,
OutputIterator result,
Function2 func)
- Execute a function object on every two elements in two ranges, storing
the result into a third (or the same) range.
transform
assigns through every iterator in the
range [result,...)
a new corresponding value equal to
func(i1.get(), i2.get())
for each i1
and i2
in the range [first1,last1)
and [first2,...)
.
- Parameters:
- first1 - The beginning of the range
- last1 - The end of the range.
- first2 - The beginning of the second range
- result - The beginning of the result range
- Returns:
- An iterator pointing past-the-end of the result range.
replace
public static void replace(ForwardIterator first,
ForwardIterator last,
Object oldvalue,
Object value)
- Replace all elements in the range which match a value,
with another value.
replace
substitutes elements in the range
[first,last)
with value
when
i.get().equals(oldvalue) == true
.
All other elements remains unaffected.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- oldvalue - The elements to be replaced must match oldvalue.
- value - The replacement value.
replace
public static void replace(ForwardIterator first,
ForwardIterator last,
Predicate1 pred,
Object value)
- Replace all element in the range which satisfy a predicate with
another value.
replace
substitutes elements in the range
[first,last)
with value
when
pred(i.get()) == true
.
All other elements remains unaffected.
- Parameters:
- pred - the predicate that must be true for the element
to be replaced.
- value - the replacement value.
- first - The beginning of the range
- last - The end of the range.
- pred - The rpedicate that must be satisfied.
- value - The replacement value.
fill
public static void fill(ForwardIterator first,
ForwardIterator last,
Object value)
- Assign a value to all elements in the range.
fill
fills the range [first,last)
with the value
.
Note that all elements will share a reference to the same value.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- value - the value that is inserted into the range.
fill
public static OutputIterator fill(OutputIterator first,
int n,
Object value)
- Assign a value to all elements in the range.
fill
fills the range [first,first+n)
with the value
.
Note that all elements will share a reference to the same value.
- Parameters:
- first - The beginning of the range
- n - The number of times the value will be inserted.
- value - The value that is inserted into the range.
- Returns:
- An iterator pointing past-the-end of the range.
generate
public static void generate(ForwardIterator first,
ForwardIterator last,
Function0 func)
- Assign the result of a function object to all elements in the range.
generate
invokes the function object func
and assigns the return value of func
through all the
iterators in the range [first,last)
.
func
takes no arguments.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- func - The function object performed one time for
each element inserted.
generate
public static OutputIterator generate(OutputIterator first,
int n,
Function0 func)
- Assign the result of a function object to all elements in the range.
generate
invokes the function object func
and assigns the return value of func
through all the
iterators in the range [first, first+n)
.
func
takes no arguments.
- Parameters:
- first - The beginning of the range
- n - The number of times func will be executed.
- func - The function object performed one time for
each element inserted.
- Returns:
- An iterator pointing past-the-end of the range.
remove
public static ForwardIterator remove(ForwardIterator first,
ForwardIterator last,
Object value)
- Remove all elements in the range which match a value.
remove
eliminates all the elements referred to by
iterator i
in the range [first,last)
for which i.get().equals(value) == true
.
Returns the past-the-end of the resulting range.
remove
is stable, that is, the relative order of the
elements that are not removed is the same as the
relative order in the original range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- value - Only elements equal to value is removed.
- Returns:
- An iterator pointing past-the-end of the resulting range.
remove
public static ForwardIterator remove(ForwardIterator first,
ForwardIterator last,
Predicate1 pred)
- Remove all elements in the range which satisfy a predicate.
remove
eliminates all the elements referred to by
iterator i
in the range [first,last)
for which pred(i.get()) == true
.
Returns the past-the-end of the resulting range.
remove is stable, that is, the relative order of the
elements that are not removed is the same as the
relative order in the original range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate that must be true for
elements to be removed
- Returns:
- An iterator pointing past-the-end of the resulting range.
remove_copy
public static OutputIterator remove_copy(InputIterator first,
InputIterator last,
OutputIterator result,
Object value)
- Copy all elements in the range except those matching a value.
remove_copy
copies all the elements referred to by the
iterator i
in the range [first,last)
for which i.get().equals(value) == false
.
remove_copy
returns the past-the-end iterator for the
resulting range.
remove_copy
is stable, that is, the relative order of the
elements in the resulting range is the same as the
relative order in the original range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- value - Only elements not equal to value is copied.
- Returns:
- An iterator pointing past-the-end of the resulting range.
remove_copy
public static OutputIterator remove_copy(InputIterator first,
InputIterator last,
OutputIterator result,
Predicate1 pred)
- Copy all elements in the range except those which satidfy a predicate.
remove_copy
copies all the elements referred to by the
iterator i
in the range [first,last)
for which pred(i.get()) == false
.
remove_copy
returns the past-the-end iterator for the
resulting range.
remove_copy
is stable, that is, the relative order of the
elements in the resulting range is the same as the
relative order in the original range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate that must be false for
elements to be copied.
- Returns:
- An iterator pointing past-the-end of the resulting range.
unique
public static ForwardIterator unique(ForwardIterator first,
ForwardIterator last)
- Remove all but the first element from every consecutive
group of equal elements.
unique
eliminates all but the first element
from every consecutive group of equal elements
referred to by the iterator i
in
the range [first,last)
for which
i.get().equals(i.prev().get()) == true
.
unique
return the end of the resulting range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- Returns:
- An iterator pointing past-the-end of the resulting range.
unique
public static ForwardIterator unique(ForwardIterator first,
ForwardIterator last,
Predicate2 pred)
- Remove all but the first element from every consecutive
group of equal elements when comparing with a predicate.
unique
eliminates all but the first element
from every consecutive group of equal elements
referred to by the iterator i
in
the range [first,last)
for which
pred(i.get(), i.prev().get()) == true
.
unique
return the end of the resulting range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate used for comparing elements.
- Returns:
- An iterator pointing past-the-end of the resulting range.
unique_copy
public static OutputIterator unique_copy(InputIterator first,
InputIterator last,
OutputIterator result)
- Copy only the first element from every consecutive
group of equal elements.
unique_copy
copies only the first element
from every consecutive group of equal elements
referred to by the iterator i
in
the range [first,last)
for which
i.get().equals(i.prev().get()) == true
.
unique_copy
returns the end of the resulting range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- Returns:
- An iterator pointing past-the-end of the resulting range.
unique_copy
public static OutputIterator unique_copy(InputIterator first,
InputIterator last,
OutputIterator result,
Predicate2 pred)
- Copy only the first element from every consecutive
group of equal elements when comparing with a predicate.
unique_copy
copies only the first element
from every consecutive group of equal elements
referred to by the iterator i
in
the range [first,last)
for which
pred(i.get(), i.prev().get()) == true
.
unique_copy
returns the end of the resulting range.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate used for comparing elements.
- Returns:
- An iterator pointing past-the-end of the resulting range.
reverse
public static void reverse(BidirectionalIterator first,
BidirectionalIterator last)
- Reverse the elements in the range.
For each integer
i <= N/2
, reverse
applies swap to all pairs of iterators
first+i, last-i-1
.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
reverse
public static void reverse(RandomIterator first,
RandomIterator last)
- Reverse the elements in the range.
For each integer
i <= N/2
, reverse
applies swap to all pairs of iterators
first+i, last-i-1
.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
rotate
public static void rotate(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last)
- Shift elements in the range leftwards.
For each non-negative integer
i < N
, rotate
places the element from the position first+i
into
position first+(i+(last-middle)) % N
.
[first,middle)
and [middle,last)
must
be valid ranges.
- Parameters:
- first - The beginning of the range
- middle - The middle of the range.
- last - The end of the range.
rotate
public static void rotate(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last)
- Shift elements in the range leftwards.
For each non-negative integer
i < N
, rotate
places the element from the position first+i
into
position first+(i+(last-middle)) % N
.
[first,middle)
and [middle,last)
must
be valid ranges.
- Parameters:
- first - The beginning of the range
- middle - The middle of the range.
- last - The end of the range.
rotate
public static void rotate(RandomIterator first,
RandomIterator middle,
RandomIterator last)
- Shift elements in the range leftwards.
For each non-negative integer
i < N
, rotate
places the element from the position first+i
into
position first+(i+(last-middle)) % N
.
[first,middle)
and [middle,last)
must
be valid ranges.
- Parameters:
- first - The beginning of the range
- middle - The middle of the range.
- last - The end of the range.
rotate_copy
public static OutputIterator rotate_copy(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last,
OutputIterator result)
- Shift elements in the range leftwards, placing the result
into another range.
rotate_copy
copies the range [first,last)
to
the range [result,...)
such that
*(result+(i+(last-middle)) % N = *(first+i)
.
rotate_copy
returns a past-the-end iterator of the result.
- Parameters:
- first - The beginning of the range
- middle - The middle of the range.
- last - The end of the range.
random_shuffle
public static void random_shuffle(RandomIterator first,
RandomIterator last)
- Randomly reorders the elements in the range.
random_shuffle
shuffles the elements in
range [first,last)
with uniform distribution.
Exactly N - 1
swaps are done.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
random_shuffle
public static void random_shuffle(RandomIterator first,
RandomIterator last,
RandomGenerator rd)
- Randomly reorders the elements in the range using
a random generator.
random_shuffle
shuffles the elements in
range [first,last)
with uniform distribution.
The random number generator function object rand
must take a positive argument n
and return
randomly chosen values between 0 and n-1
Exactly N - 1
swaps are done.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- rand - The random number generator.
partion
public static BidirectionalIterator partion(BidirectionalIterator first,
BidirectionalIterator last,
Predicate1 pred)
- Place all elements satisfying a predicate before those
element than to not satisfy the predicate.
partition
places all the elements in the
range [first,last)
that satisfy pred
before all the elements that do not satisfy it.
It returns an iterator such that all
elements [first,i)
, pred
is
true
and for all elements [i,last)
pred
is false
.
The predicate is tested exactly N
times.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate used when testing.
stable_partion
public static BidirectionalIterator stable_partion(BidirectionalIterator first,
BidirectionalIterator last,
Predicate1 pred)
- Place all elements satisfying a predicate before those
element than to not satisfy the predicate while maintaing
the relative order of elements.
stable_partition
places all the elements in the
range [first,last)
that satisfy pred before
all the elements that do not satisfy it.
It returns an iterator such that all
elements [first,i)
, pred
is true
and for all elements [i,last)
pred
is false
.
The relative order of the elements in both
groups is preserved.
The predicate is tested exactly N
times.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate used when testing.
sort
public static void sort(RandomIterator first,
RandomIterator last,
Predicate2 pred)
- Sort the elements in the range according to the
comparison predicate pred.
sort
sorts the element in the range
[first,last)
.
It does approximatly NlogN
comparisons on the average.
If the worst case behaivior is important stable_sort
or partial_sort
should be used.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate used when testing.
stable_sort
public static void stable_sort(RandomIterator first,
RandomIterator last,
Predicate2 pred)
- Sort the elements in the range according to the
comparison predicate pred.
stable_sort
sorts the element in the range
[first,last)
.
It is stable, that is, the relative order of the equal
elements is preserved. It does at most N(logN)2
comparisons; if enough extra memory is available, it is
NlogN
.
- Parameters:
- first - The beginning of the range
- last - The end of the range.
- pred - The predicate used when testing.
nth_element
public static void nth_element(RandomIterator first,
RandomIterator nth,
RandomIterator last,
Predicate2 pred)
- Place an element of a sequence in the location where it
would be if the sequence was sorted.
After
nth_element
the element in the position
pointed to by nth
is the element that would be in that
position if the whole range was sorted. Also for any iterator
i
in the range [first, nth)
and
any iterator j
in the range [nth, last)
it holds that pred(i.get(), j.get()) == false
.
It is linear on the average.
- Parameters:
- first - The beginning of the range.
- nth - The position into the range.
- last - The end of the range.
- pred - The predicate used when testing.
lower_bound
public static ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,
Object value,
Predicate2 pred)
- Find the first position into which a value can be inserted
without violation the ordering.
lower_bound
finds the first position where
value
can be inserted. lower_bound
returns
the furthermost iterator i
in the range
[first,last)
such that for any iterator j
in the range [first,i)
the following condition holds:
pred(j.get(), value) == true
.
At most log(N) + 1
comparisons are done.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- value - The value tested against.
- pred - The predicate used when testing.
upper_bound
public static ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last,
Object value,
Predicate2 pred)
- Find the furthermost position into which a value can be inserted
without violation the ordering.
upper_bound
finds the furthermost position where
value
can be inserted. upper_bound
returns
the furthermost iterator i
in the range
[first,last)
such that for any iterator j
in the range [first,i)
the following condition holds:
pred(value, j.get()) == false
.
At most log(N) + 1
comparisons are done.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- value - The value tested against.
- pred - The predicate used when testing.
equal_range
public static Pair equal_range(ForwardIterator first,
ForwardIterator last,
Object value,
Predicate2 pred)
- Find the largest subrange into which a value can be inserted
without violation the ordering.
equal_range
finds the largest subrange
[i,j)
such that the value value
can be
at any iterator k
in it.
k
satisfy the condition
pred(k.get(), value) == false && pred(value, k.get())
.
At most 2 * log(N) + 1
comparisons are done.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- value - The value tested against.
- pred - The predicate used when testing.
binary_search
public static boolean binary_search(ForwardIterator first,
ForwardIterator last,
Object value,
Predicate2 pred)
- Returns true is the value is in the range.
binary_search
returns true
if there
is an iterator i
in the range [first,last)
that satisfy the condition
pred(i.get(), value) == false && pred(value, i.get()) == false
.
At most log(N) + 1
comparisons are done.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- value - The value tested against.
- pred - The predicate used when testing.
merge
public static OutputIterator merge(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
OutputIterator result,
Predicate2 pred)
- Merge the two sorted ranges and place the result into the result range.
merge
merges the two sorted ranges
[first1,last1)
and [first2,last2)
into
the range [result,...)
. The merge is stable,
that is, for equal elements in the two ranges, the element from
the first range always precede the element from the second range.
merge
return past-the-end of the result range.
The result of merge
is undefined if the resulting
range overlaps with either of the orignal ranges.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- result - The beginning of the resulting range.
- pred - The predicate used when testing.
- Returns:
- The end of the resulting range.
inplace_merge
public static void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
Predicate2 pred)
- Merge the two sorted ranges and place the result into the result range.
inplace_merge
merges the two sorted ranges
[first1,last1)
and [first2,last2)
into
the range [result,...)
. The merge is stable,
that is, for equal elements in the two ranges, the element from
the first range always precede the element from the second range.
merge
return past-the-end of the result range.
The result of merge
is undefined if the resulting
range overlaps with either of the orignal ranges.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- result - The beginning of the resulting range.
- pred - The predicate used when testing.
- Returns:
- The end of the resulting range.
includes
public static boolean includes(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
Predicate2 pred)
- Return
true
if all the elements in range2 also is in range2.
includes
return true
if every element in the
range [first2,last2)
is contained in the range
[first1,last1)
.
It returns false
otherwise.
At most (N1+N2)*2-1
comparisons are performed.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- pred - The predicate used when testing.
- Returns:
- true if range2 in included in range1.
set_union
public static OutputIterator set_union(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
OutputIterator result,
Predicate2 pred)
- Create the union of the two ranges.
set_union
constructs a sorted union of the elements
from the two ranges. It returns the end of the constructed range.
set_union
is stable, that is, if an element is present
in both ranges, the one from the first range is copied.
At most (N1+N2)*2-1
comparisons are performed.
The result of set_union
is undefined if the resulting
range overlaps with either of original ranges.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- result - The beginning of the resulting range.
- pred - The predicate used when testing.
- Returns:
- The end of the result range.
set_intersection
public static OutputIterator set_intersection(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
OutputIterator result,
Predicate2 pred)
- Create the intersection of the two ranges.
set_intersection
constructs a sorted intersection of the elements
from the two ranges. It returns the end of the constructed range.
set_intersection
is guarenteed to be stable, that is,
if an element is present in both ranges, the one from the first range
is copied.
At most (N1+N2)*2-1
comparisons are performed.
The result of set_intersection
is undefined if the resulting
range overlaps with either of original ranges.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- result - The beginning of the resulting range.
- pred - The predicate used when testing.
- Returns:
- The end of the result range.
set_difference
public static OutputIterator set_difference(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
OutputIterator result,
Predicate2 pred)
- Create the difference of the two ranges.
set_difference
constructs a sorted difference of the elements
from the two ranges. It returns the end of the constructed range.
At most (N1+N2)*2-1
comparisons are performed.
The result of set_difference
is undefined if the resulting
range overlaps with either of original ranges.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- result - The beginning of the resulting range.
- pred - The predicate used when testing.
- Returns:
- The end of the result range.
set_symmetric_difference
public static OutputIterator set_symmetric_difference(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
OutputIterator result,
Predicate2 pred)
- Create the symmetric difference of the two ranges.
set_symmetric_difference
constructs a sorted symmetric
difference of the elements from the two ranges.
It returns the end of the constructed range.
At most (N1+N2)*2-1
comparisons are performed.
The result of set_symmetric_difference
is undefined if the resulting
range overlaps with either of original ranges.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- result - The beginning of the resulting range.
- pred - The predicate used when testing.
- Returns:
- The end of the result range.
push_heap
public static void push_heap(RandomIterator first,
RandomIterator last,
Predicate2 pred)
- Place a new value into the heap.
push_heap
assumes the range [first,last.prev())
is a valid heap and properly places the value in the location
last.prev()
into the resulting heap
[first,last)
.
At most log(N)
comparisons are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
pop_heap
public static void pop_heap(RandomIterator first,
RandomIterator last,
Predicate2 pred)
- Remove the largest value from the heap.
pop_heap
assumes the range [first,last)
is a valid heap, then swaps the value in the location
first()
with the value in the location
last.prev()
and makes [first,last.prev())
into a heap.
At most 2*log(N)
comparisons are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
make_heap
public static void make_heap(RandomIterator first,
RandomIterator last,
Predicate2 pred)
- Create a heap out of a sequence.
make_heap
construct a heap out of the range
[first,last)
.
At most 3*N
comparisons are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
sort_heap
public static void sort_heap(RandomIterator first,
RandomIterator last,
Predicate2 pred)
- Turns the heap into a sorted sequence.
sort_heap
sort the elements in the heap
[first,last)
.
At most NlogN
comparisons are performed.
sort_heap
is not stable.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
min
public static int min(int a,
int b)
- Returns the smaller of the two integers.
max
public static int max(int a,
int b)
- Returns the larger of the two integers.
min
public static char min(char a,
char b)
- Returns the smaller of the two characters.
max
public static char max(char a,
char b)
- Returns the larger of the two characters.
min
public static Object min(Object a,
Object b,
Predicate2 pred)
- Returns the smaller of two objects.
max
public static Object max(Object a,
Object b,
Predicate2 pred)
- Returns the larger of two objects.
max_element
public static ForwardIterator max_element(ForwardIterator first,
ForwardIterator last,
Predicate2 pred)
- Returns the first iterator pointing to the maximal element in the range.
max_element
return the first iterator i
in the range [first,last)
such that for any
iterator j
in the range [first,last)
the following condition holds:
pred(i.get(), j.get()) == false
.
Exactly max(N-1, 0)
comparisons are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
min_element
public static ForwardIterator min_element(ForwardIterator first,
ForwardIterator last,
Predicate2 pred)
- Returns the first iterator pointing to the minimal element in the range.
min_element
return the first iterator i
in the range [first,last)
such that for any
iterator j
in the range [first,last)
the following condition holds:
pred(j.get(), i.get()) == false
.
Exactly max(N-1, 0)
comparisons are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
lexicographical_compare
public static boolean lexicographical_compare(InputIterator first1,
InputIterator last1,
InputIterator first2,
InputIterator last2,
Predicate2 pred)
- Compares two sequences lexicographically and return true if
range1 is less than range2.
lexicographical_compare
return true
if the
sequence of elements defined by the range [first1,last1)
is
if lexicographically less than the sequence of elements defined
by the range [first2,last2)
.
it returns false
otherwise.
At most 2 * min(N1, N2)
comparisons are performed.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- pred - The predicate used when testing.
next_permutation
public static boolean next_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Predicate2 pred)
- Permutates the sequence into its successor.
next_permutation
takes a sequence defined by the range
[first,last)
and transform it into the next
permutation.
The next permutation if found by assuming that set set of all permutation
is lexicographiclly sorted with respect to pred
.
If such a permutation exist, it returns true
.
Otherwise, it transform the sequence into the smallest permutation,
that is, the ascending sorted one, and returns false
.
At most N/2
swaps are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
prev_permutation
public static boolean prev_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Predicate2 pred)
- Permutates the sequence into its predecessor.
prev_permutation
takes a sequence defined by the range
[first,last)
and transform it into the previous
permutation.
The previous permutation if found by assuming that set set of all
permutation is lexicographiclly sorted with respect to
pred
.
If such a permutation exist, it returns true
.
Otherwise, it transform the sequence into the largest permutation,
that is, the descending sorted one, and returns false
.
At most N/2
swaps are performed.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- pred - The predicate used when testing.
accumulate
public static Object accumulate(InputIterator first,
InputIterator last,
Object init,
Function2 func)
- Accumulate over the range.
accumulate
initializes the the accumulator acc
with the initial value init
and then performing
acc = func(acc, i.get())
for every iterator
i
in the range [first,last)
in order.
func
is assumed not to cause side effects.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- init - The initial value.
- func - The binary function.
- Returns:
- The resulting value of
acc
.
inner_product
public static Object inner_product(InputIterator first1,
InputIterator last1,
InputIterator first2,
Object init,
Function2 func1,
Function2 func2)
- Compute the inner product of two ranges.
inner_product
initializes the accumulator acc
with the initial value init
and then performing
acc = func1(acc, func2(i1.get(), i2.get()))
for every iterator i1
in the range
[first1,last1)
and every iterator i2
in the range [first2,last2)
in order.
func1
and func2
is assumed not to cause
side effects.
- Parameters:
- first1 - The beginning of the first range.
- last1 - The end of the first range.
- first2 - The beginning of the second range.
- last2 - The end of the second range.
- init - The initial value.
- func1 - The binary function used for accumulation.
- func2 - The binary function used for multiplying.
- Returns:
- The resulting value of
acc
.
partial_sum
public static Object partial_sum(InputIterator first,
InputIterator last,
OutputIterator result,
Function2 func)
- Computes the partial sum of the elements in the range.
partial_sum
assigns to every iterator i
in the range [result,...)
a value equal to
func2(func2(..., func2(first.get(), first.get(1)), ... ), first.get(i-result)))
.
partial_sum
return the end of the result range.
Exactly N-1
applications of func are performed.
func
is assumed not to cause side effects.
result
may be equal to first
.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- result - The resulting range.
- func - The binary function.
- Returns:
- The end of the resulting range.
adjacent_difference
public static OutputIterator adjacent_difference(InputIterator first,
InputIterator last,
OutputIterator result,
Function2 func)
- Computes the adjancent difference of the elements in the range.
adjancent_difference
assigns to every element
element referred to be iterator i
in the range [result+1,...)
a value equal to
func(first.get(i-result), first.get(i-result-1))
.
result
gets the value of first.get()
.
adjancent_difference
returns the end of the result range.
Exactly N-1
applications of func are performed.
func
is assumed not to cause side effects.
result
may be equal to first
.
- Parameters:
- first - The beginning of the range.
- last - The end of the range.
- result - The resulting range.
- func - The binary function.
- Returns:
- The end of the resulting range.
iota
public static void iota(ForwardIterator first,
ForwardIterator last,
Object value,
Function2 func,
Object incr)
- XXX.
All Packages Class Hierarchy This Package Previous Next Index